/*
 * @lc app=leetcode.cn id=18 lang=cpp
 *
 * [18] 四数之和
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        //类似三数之和

        std::sort(nums.begin(), nums.end());

        vector<vector<int>> results;

        //四数之和 比 三数之和 多一层循环
        for (int i = 0; i < nums.size(); i++) {
            
            //组外去重 1
            if (i > 0 && nums[i] == nums[i - 1])
                continue;

            for (int j = i + 1; j < nums.size(); j++) {

                //组外去重 2
                if (j > (i + 1) && nums[j] == nums[j - 1])
                    continue;

                int l = j + 1, r = nums.size() - 1;

                while (l < r) {
                    int64_t t = static_cast<uint64_t>(nums[i]) +
                                 static_cast<uint64_t>(nums[j]) + 
                                 static_cast<uint64_t>(nums[l]) +
                                 static_cast<uint64_t>(nums[r]);
                    
                    if (t == target) {
                        results.push_back(vector<int>{ 
                            nums[i], nums[j],
                            nums[l], nums[r]
                        });

                        //组内去重
                        while(l < r && nums[l] == nums[l + 1]) l++;
                        while(l < r && nums[r] == nums[r - 1]) r--;

                        l++;
                        r--;
                    }

                    else if (t > target)
                        r--;
                    
                    else
                        l++;
                }
            }
        }

        return results;
    }
};
// @lc code=end

